class Solution {
public:
    vector<int> father,size;
    int find(int x){
        if(x != father[x]){
            father[x] = find(father[x]);
        }
        return father[x];
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        if(x > y){
            swap(x,y);
        }
        father[y] = x;
        size[x] += size[y];
    }
    
    int largestComponentSize(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int m = nums[n-1];
        
        father.resize(m+1);
        size.resize(m+1,1);
        
        for(int i = 0;i <= m;i++){
            father[i] = i;
        }
        
        for(int& i : nums){
            for(int j = 2;j * j <= i;j++){
                if(i % j == 0){
                    Union(j,i);
                    Union(i/j,j);
                }
            }
        }
        
        int ret = 0;
        vector<int> count(m+1);
        for(int i = 0;i < n;i++){
            int root = find(nums[i]);
            count[root]++;
            ret = max(count[root],ret);
        }
        
        return ret;
    }
};
